#include "p2.h"


	string file;
	ofstream output;
	bool tiempo = false;

string get_file_contents(const char *filename){
	ifstream in(filename, std::ios::in | std::ios::binary);
	if (in){
		string contents;
		in.seekg(0, std::ios::end);
		contents.resize(in.tellg());
		in.seekg(0, std::ios::beg);
		in.read(&contents[0], contents.size());
		in.close();
		return(contents);
	}
	perror("Error:");
	return 0;
}

int main(int argc, char *argv[]) {
    	
	if(argc ==1){
		cout << "Usando p2.in y p2.out" << endl;
		file = get_file_contents("p2.in");
		output.open("p2.out");
		if(output.fail()){
			cerr << "Error al abrir archivo de salida" << endl;
		}
	}

	else if(argc ==3){
		cout << "Usando " << argv[1] << " y " << argv[2] << endl;
		file = get_file_contents(argv[1]);
		output.open(argv[2]);
		if(output.fail()){
			cerr << "Error al abrir archivo de salida" << endl;
		}
	}

	else if(argc ==2 && string (argv[1]) == "time"){
		cout << "Calculando tiempos usando p2.in y p2.out con " << ITER << " iteraciones" << endl;
		tiempo = true;
		file = get_file_contents("p2.in");
		output.open("p2.out");
		if(output.fail()){
			cerr << "Error al abrir archivo de salida" << endl;
		}
	}

	else{
		cout << "Modo de uso: \"p2 input output\" o \"p2 time\" para benchmark" << endl;
		return 0;
    }

	istringstream input;
	input.str(file);
	while(!input.eof()){
		if(input.peek() == '#'){
			break;
		}
		string l;
		int n;
		
		getline(input,l);
		istringstream ssl(l);		
		
		ssl >> n;
		list<camino> caminos = cargar(input,n);
		if(tiempo){
			list<camino> solCaminos;
			uint64_t t;
			uint64_t res = 0;
			for(int i=0;i<ITER;i++){
				t=rdtsc();
				resolver(n,caminos,solCaminos);
				t = rdtsc() -t;
				res = res + t;
			}
		res = res/ITER;
		cout << "For n= " << n << " process took: "<< res << " ticks" << endl;
		}
		list<camino> solCaminos;
		int sol = resolver(n,caminos,solCaminos);
		salida(output,sol,solCaminos);
	}
	output.close();
	return 0;
}

list<camino> cargar(istringstream& is, int n){
	string l;
    int cantCaminos = (n*(n-1)/2);
    list<camino> caminos;
	int c1 = 0;
	int c2 = 0;
	int e = 0;
	int p = 0;
	for(int i=0; i < cantCaminos; i++){
		getline(is,l);
		istringstream ssl(l);
		ssl >> c1;
		ssl >> c2;
		ssl >> e;
		ssl >> p;
        if (e == 1){
        	p = p * (-1);
        }
        camino nuevoC(c1,c2,p);

        caminos.push_back(nuevoC);
	}
	caminos.sort();
	return caminos;
}

int resolver(const int n, const list<camino> &caminos,list<camino> &solucion){
	int costoTotal = 0;
	bosque b(n);
	
	std::list<camino>::const_iterator it;
	for (it=caminos.begin(); (it!=caminos.end()&& solucion.size()<(unsigned int)(n-1)); it++){
		int c1 = (*it).c1;
		int c2 = (*it).c2;      
		if (b.combinar(c1,c2)){	//Si los arboles son distintos (y se combinan en 1 solo)
			solucion.push_back(*it);
			if ((*it).costo>0){
				costoTotal += (*it).costo;
			}
		}else{
			//Si pertenecian al mismo arbol, no puedo elegir esa arista
			if ((*it).costo<0){ //Si estaba construida sumo el costo
				costoTotal = costoTotal - (*it).costo;
			}
		}        
	}
	while (it!=caminos.end() && ((*it).costo<0)) { //Sumo los valores de las rutas construidas que puede haber quedado
		costoTotal = costoTotal - (*it).costo;
		it++;
	}
	return costoTotal;
}
void salida(ostream& out, int sol,list<camino> &caminos){	
	out << sol << " " << caminos.size();
	std::list<camino>::iterator it;	
	for (it=caminos.begin(); it!=caminos.end(); ++it){
		out << " " << (*it).c1 << " " << (*it).c2;
	}
	out << endl;
}

bosque::bosque(int c){
	//Genero un bosque de arboles que contienen 1 solo nodo 
	for (int i=0;i<c;i++){
		nodo* nuevoNodo = new nodo();
		nuevoNodo->padre = NULL;
		nuevoNodo->altura = 1;
		arboles.push_back(nuevoNodo);
	}
}

bosque::~bosque(){
	for (unsigned int i=0;i<arboles.size();i++){
		delete arboles[i];
	}
}

bool bosque::combinar(int c1,int c2){
	nodo* raiz1 = arboles[c1-1];
	while (raiz1->padre!=NULL){
		raiz1 = raiz1->padre;
	}
	nodo* raiz2 = arboles[c2-1];
	while (raiz2->padre!=NULL){
		raiz2 = raiz2->padre;
	}
	if (raiz1==raiz2){
		//Si es el mismo arbol salgo
		return false;
	}
	//Si son arboles distintos
	if (raiz1->altura>raiz2->altura){
		raiz2->padre = raiz1;
	}else{
		if (raiz1->altura==raiz2->altura)		
		raiz2->altura = raiz2->altura + 1;
		raiz1->padre = raiz2;
	}
	return true;	
}
